package top;

/**
 *
 * 二叉树的最近公共祖先
 *
 * @author chenyw
 * @date 2022/7/19 19:37
 */
public class Top236lowestCommonAncestor {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return dfs(root, p, q);
    }

    private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        //这一步先写上面，如果在一边子树找到了那么这棵子树就不用再找了，去另一边找，另一边如果没有那说明另一个节点也在这一边，并且是root的子节点
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = dfs(root.left, p, q);
        TreeNode right = dfs(root.right, p, q);
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        //左右子树都不为null，说明p和q正好在其两侧，返回root
        return root;
    }
}
